#include <iostream>
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} NODE;


//尾插法
void List_tail_insert(NODE *&L) {
    L = (NODE *) malloc(sizeof(NODE));//申请头指针
    int num;
    NODE *q, *p;
    q = L;//将头结点的位置赋给头指针
    scanf("%d", &num);
    while (num != 9999) {
        p = (NODE *) malloc(sizeof(NODE));
        p->data = num;
        q->next = p;//将新结点的位置赋给尾结点的next指针
        q = p;//将指针地址赋给下一个指针
        scanf("%d", &num);
    }
    p->next = NULL;//将尾指针的数据域置为NULL
}

//找到链表中间结点，并设置好L2链表
void find_middle(NODE *L, NODE *&L2) {
    L2 = (NODE *) malloc(sizeof(NODE));//申请第二条链表的头结点的空间
    NODE *pcur, *ppre;//双指针遍历是考研初试常考的
    ppre = pcur = L->next;
    while (pcur) {
        pcur = pcur->next;
        //需在跳两步前进行判断，万一链表只有一个结点的情况
        if (pcur == NULL) {//为了防止pur为NULL
            break;
        }
        pcur = pcur->next;
        if (pcur == NULL) {//为了使得偶数个的时候，ppre依然指向a1,a2,到a6中的a3结点
            break;
        }
        ppre = ppre->next;
    }
    L2->next = ppre->next;//由L2头结点指向后面一半链表
    ppre->next = NULL;//前一半链表的最后一个结点next置为NULL

}

//链表输出
void Print_list(NODE *L) {
    L = L->next;
    while (L) {
        printf("%3d ", L->data);
        L = L->next;
    }
    printf("\n");
}

//反转链表
void reverse(NODE *L2) {
    NODE *r, *s, *t;
    r = L2->next;
    if (r == NULL) {
        return;//链表为空
    }
    s = r->next;
    if (s == NULL) {
        return;//链表只有一个结点
    }
    t = s->next;
    while (t) {
        s->next = r;//原地逆置
        //以下代码是三个指针同时往后走一步
        r = s;
        s = t;
        t = t->next;
    }
    s->next = r;
    L2->next->next = NULL;//逆置后，链表的第一个结点的next要为NULL
    L2->next = s;//s是链表的第一个结点，L2指向他
}

//合并两个链表
void merge(NODE *L, NODE *L2) {
    NODE *pcur, *q, *p;
    pcur = L->next;//pcur始终指向组合后链表的链表尾
    p = pcur->next;//p用来遍历L1链表
    q = L2->next;//q指向L2的第一个结点，q用来遍历L2链表
    //
    while (p != NULL && q != NULL) {
        pcur->next = q;
        q = q->next;//指向下一个结点
        pcur = pcur->next;
        pcur->next = p;
        p = p->next;//指向下一个
        pcur = pcur->next;
    }
    //任何一个链表都可能剩余一个结点，放进来即可
    if (p != NULL) {
        pcur->next = p;
    }
    if (q != NULL) {
        pcur->next = q;
    }
}

int main() {
    NODE *L;//链表头，是结构体指针类型
    NODE *search;//用来存储拿到的某一个结点
    List_tail_insert(L);
    Print_list(L);//链表打印

    //寻找中间结点，并返回第二条链表
    NODE *L2 = NULL;
    find_middle(L, L2);//只有一个结点时，L2中是没有结点的
    printf("--------------------------------\n");
    Print_list(L);
    Print_list(L2);
    printf("--------------------------------\n");
    reverse(L2);
    Print_list(L2);
    printf("--------------------------------\n");
    merge(L, L2);
    free(L2);
    Print_list(L);
    return 0;
}


